package backtracking.leetcode.medium;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author bruin_du
 * @description 迷宫中离入口最近的出口
 * @date 2022/9/15 23:43
 **/
public class Num1926_NearestExit {
    int[][] dics = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public int nearestExit(char[][] maze, int[] entrance) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrance);
        maze[entrance[0]][entrance[1]] = '+';
        int step = 0, m = maze.length, n = maze[0].length;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            while (size-- > 0) {
                int[] index = queue.poll();
                for (int[] dic : dics) {
                    int row = index[0] + dic[0];
                    int col = index[1] + dic[1];
                    if (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == '.') {
                        if (row == 0 || row == m - 1 || col == 0|| col == n - 1){
                            return step;
                        }
                        queue.offer(new int[]{row, col});
                        maze[row][col] = '+';
                    }
                }
            }
        }
        return -1;
    }
}
